I capitoli precedenti hanno risolto i problemi di prediction (valutare una policy) e di control (trovare la policy ottima) in un MDP sotto un’ipotesi molto forte: la conoscenza completa del modello, cioè della dinamica one-step $p(s' \mid s, a)$ e della funzione di reward $r(s, a)$. Con il modello in mano, la programmazione dinamica trova la policy ottima iterando le equazioni di Bellman. Questo capitolo rimuove quell’ipotesi e affronta la domanda che apre il reinforcement learning vero e proprio: che cosa si può fare quando il modello non c’è, oppure costruirlo è troppo difficile o costoso? La risposta dei metodi Monte Carlo è tanto semplice quanto potente: sostituire i valori attesi calcolati attraverso il modello con medie empiriche calcolate sull’esperienza, cioè su episodi completi di interazione con l’ambiente. Il percorso del capitolo parte dalla motivazione del model-free, sviluppa la Monte Carlo prediction (stimatori first-visit ed every-visit, aggiornamento incrementale della media), passa al control scoprendo che il vero ostacolo è l’esplorazione, introduce le soluzioni exploring starts e policy ε-greedy con il relativo teorema di improvement e la condizione GLIE, distingue apprendimento on-policy e off-policy con l’importance sampling, discute i limiti strutturali dei metodi Monte Carlo e chiude con esercizi numerici svolti nello stile tipico dell’esame.

Riferimenti sul testo: Sutton e Barto, Reinforcement Learning: An Introduction, capitolo 5. Materiale complementare consigliato: il corso online Sample-based Learning Methods (Coursera).

1. E se il modello non c’è? Dal planning all’apprendimento#

1.1 Il limite della programmazione dinamica#

Gli algoritmi di programmazione dinamica, come value iteration, aggiornano la value function con backup del tipo

$$V(s) \leftarrow \max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V(s') \right]$$

Ogni singolo aggiornamento richiede di conoscere $r(s, a)$ e $p(s' \mid s, a)$, cioè la dinamica one-step dell’MDP: sono esattamente i due ingredienti che le slide del corso evidenziano nella formula del backup.

Le difficoltà di questo approccio sono di due nature. La prima è computazionale: anche con il modello disponibile, gli sweep su tutto lo spazio degli stati limitano la programmazione dinamica a problemi con al più qualche milione di stati (esistono mitigazioni, come la programmazione dinamica asincrona che aggiorna gli stati in ordine sparso e in parallelo, ma il costo resta proibitivo per spazi molto grandi). La seconda difficoltà è più radicale e riguarda la disponibilità stessa del modello: nella stragrande maggioranza dei problemi reali la dinamica one-step non è nota, e costruirne un modello accurato può essere estremamente complesso, dispendioso o semplicemente impossibile.

L’esempio del blackjack, sviluppato più avanti, è istruttivo: in linea di principio il gioco si potrebbe modellare analiticamente, calcolando la distribuzione congiunta di prossimo stato e reward per ogni situazione; in pratica scrivere quella distribuzione è un esercizio laborioso e soggetto a errori, mentre scrivere un simulatore che pesca carte e applica le regole è questione di poche righe di codice. Serve quindi una famiglia di metodi che non chieda il modello, ma si accontenti dei dati: metodi che imparino la policy ottima direttamente dall’esperienza.

Idea chiave: i metodi Monte Carlo sostituiscono la conoscenza del modello con l’esperienza: al posto dei valori attesi calcolati tramite $p(s' \mid s, a)$ usano medie empiriche di quantità osservate interagendo con l’ambiente (reale o simulato). Per la legge dei grandi numeri, con abbastanza esperienza la media converge al valore atteso.

In parole semplici: la programmazione dinamica è come calcolare la probabilità di vincere a un gioco leggendo il regolamento e facendo tutti i conti; Monte Carlo è come giocare tantissime partite e contare quante se ne vincono. Se il regolamento non ce l’ha nessuno, la seconda strada è l’unica percorribile.

1.2 Imparare dall’esperienza: episodi e return campionati#

L’esperienza da cui i metodi Monte Carlo imparano è costituita da episodi completi: sequenze di stati, azioni e reward osservati dall’inizio dell’interazione fino a uno stato terminale,

$$S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_{T-1}, A_{T-1}, R_T$$

Questi dati possono provenire da due sorgenti: dati reali, cioè tracce di interazione registrate su un problema fisico (per esempio i log di guida di un veicolo), oppure un simulatore, un programma capace di generare episodi a richiesta. In entrambi i casi non serve alcuna conoscenza esplicita della distribuzione $p(s', r \mid s, a)$. I metodi Monte Carlo si possono quindi usare in due modalità:

• model-free: nessun modello è necessario, e si raggiunge comunque l’ottimalità;
• simulated: basta un simulatore in grado di generare campioni, non un modello completo della dinamica.

La materia prima dell’apprendimento è il return campionato: alla fine di ogni episodio, per ogni istante $t$ visitato, si può calcolare il return effettivamente realizzato $G_t = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$. È un’osservazione, non un valore atteso: ogni episodio ne fornisce una realizzazione concreta. Da questa scelta discende però un vincolo strutturale: poiché il return si conosce solo quando l’episodio è terminato, i metodi Monte Carlo sono definiti solo per task episodici. Se l’interazione non termina mai, il return completo non è mai osservabile e l’idea non si applica (i metodi del prossimo capitolo rimuoveranno anche questo vincolo).

In parole semplici: Monte Carlo aspetta la fine della partita, guarda quanti punti ha totalizzato da ogni momento in poi, e usa questi punteggi osservati come campioni. Proprio perché serve il punteggio finale, il gioco deve avere una fine: su problemi che non finiscono mai questi metodi non partono nemmeno.

2. Monte Carlo prediction: stimare i valori dai return osservati#

2.1 L’idea: la media dei return#

Il problema più semplice è, come sempre, la policy evaluation: data una policy $\pi$, stimare la sua state-value function. La definizione è

$$V^{\pi}(s) = \mathbb{E}_{\pi}\left[ G_t \mid S_t = s \right]$$

cioè un valore atteso. Senza modello non si può calcolare questo valore atteso con l’equazione di Bellman; ma se si dispone di un certo numero di episodi generati seguendo proprio $\pi$ e contenenti visite a $s$, ogni visita fornisce un campione del return da $s$. Lo stimatore Monte Carlo è la media empirica di questi campioni:

$$V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_i(s)$$

dove $N(s)$ è il numero di return raccolti per lo stato $s$ e $G_i(s)$ è l’$i$-esimo return osservato a partire da una visita a $s$.

Un dettaglio da non trascurare: gli episodi devono essere generati dalla stessa policy che si vuole valutare; se i dati provenissero da un’altra policy, la media stimerebbe la value function di quell’altra policy (questo problema, tutt’altro che secondario, sarà ripreso e risolto nella sezione 8 con l’importance sampling).

Idea chiave: la Monte Carlo prediction stima $V^{\pi}(s)$ come media aritmetica dei return osservati dopo le visite a $s$ negli episodi generati da $\pi$. Nessuna equazione di Bellman, nessun modello: solo la definizione di valore atteso approssimata con una media empirica.

In parole semplici: per sapere quanto vale trovarsi in una certa situazione seguendo una strategia, si guardano tutte le volte che ci si è passati e si fa la media di quanto si è guadagnato da lì alla fine. Più volte ci si passa, più la media è affidabile.

2.2 Una sottigliezza: first-visit ed every-visit#

C’è un dettaglio tecnico che la definizione lascia aperto: che cosa fare quando lo stesso stato viene visitato più volte nello stesso episodio? Si consideri un episodio con un ciclo:

$$s_1 \to s_2 \to s_3 \to s_2 \to s_3 \to s_4 \; (\text{terminale})$$

Lo stato $s_2$ compare due volte, ai tempi $t = 1$ e $t = 3$, e lo stesso vale per $s_3$. Nel calcolare i campioni di return per $s_2$ si deve partire dalla prima occorrenza, dalla seconda, o da entrambe? Le due risposte possibili definiscono i due stimatori Monte Carlo standard.

Entrambe le scelte hanno una loro logica. A favore dell’every-visit: trovandosi in $s_2$ non si può sapere in anticipo se si imboccherà il ciclo o si andrà dritti verso il terminale; entrambi gli scenari sono realizzazioni legittime del “futuro a partire da $s_2$”, e una media empirica dovrebbe includerli tutti. A favore del first-visit: i return calcolati dalla prima visita in episodi diversi sono campioni indipendenti e identicamente distribuiti della variabile aleatoria $G_t \mid S_t = s$, il che rende lo stimatore più pulito dal punto di vista statistico.

2.3 Proprietà degli stimatori: bias, varianza, convergenza#

Le proprietà statistiche dei due stimatori sono il criterio con cui confrontarli.

• First-visit MC: ogni episodio contribuisce con al più un campione per stato, e campioni provenienti da episodi diversi sono indipendenti e identicamente distribuiti. La media è quindi uno stimatore non distorto (unbiased) di $V^{\pi}(s)$ per ogni numero di campioni, e per la legge dei grandi numeri converge a $V^{\pi}(s)$; l’errore standard della stima decresce come $1/\sqrt{N(s)}$.
• Every-visit MC: i return calcolati da visite diverse dello stesso episodio si sovrappongono (condividono parte della coda di reward) e sono quindi correlati tra loro; lo stimatore risulta distorto (biased) per un numero finito di campioni. Il bias però svanisce al crescere dei dati: lo stimatore è consistente e converge anch’esso a $V^{\pi}(s)$. In compenso estrae più campioni da ogni episodio, quindi sfrutta di più i dati disponibili.

Entrambi convergono asintoticamente alla vera value function: la scelta tra i due, in pratica, dipende soprattutto dalla convenienza implementativa, e ai fini del corso vanno considerati due varianti equivalenti dello stesso metodo.

In parole semplici: first-visit conta ogni episodio una volta sola per stato: campioni indipendenti, media onesta fin da subito, ma butta via un po’ di dati. Every-visit usa tutte le occorrenze: più dati per episodio, ma campioni imparentati tra loro, e la media è leggermente sbilanciata finché i dati sono pochi. Con abbastanza episodi arrivano entrambi allo stesso risultato.

2.4 L’algoritmo first-visit e il calcolo dei return all’indietro#

Il calcolo dei return per tutti gli istanti di un episodio si esegue in modo efficiente partendo dalla fine, sfruttando la ricorsione $G_t = R_{t+1} + \gamma \, G_{t+1}$: il return dell’ultimo passo è il solo reward finale, e ogni passo precedente si ottiene con una somma e una moltiplicazione. Procedere in avanti, ricalcolando ogni volta l’intera somma scontata, sarebbe molto più costoso. Lo pseudocodice della first-visit MC prediction:

Input: policy π da valutare
Inizializza: V(s) arbitraria; Returns(s) ← lista vuota, per ogni s

Ripeti per sempre (per ogni episodio):
    Genera un episodio seguendo π: S0, A0, R1, S1, A1, R2, ..., S(T-1), A(T-1), RT
    G ← 0
    Per t = T-1, T-2, ..., 0:
        G ← γ·G + R(t+1)
        Se St non compare in S0, S1, ..., S(t-1):        # prima visita a St
            aggiungi G a Returns(St)
            V(St) ← media(Returns(St))

“Genera un episodio” ha due letture concrete: con un simulatore significa far giocare l’agente dall’inizio alla fine (una partita a scacchi completa, una mano di blackjack); con dati reali significa prelevare una traiettoria registrata dal dataset. La versione every-visit si ottiene semplicemente eliminando il controllo di prima visita.

3. L’aggiornamento incrementale della media#

3.1 Dalla lista dei return alla media incrementale#

Conservare per ogni stato l’intera lista dei return osservati è uno spreco: della lista serve solo la media, e la media si può aggiornare al volo. Detta $\mu_k$ la media dei primi $k$ campioni $x_1, \dots, x_k$:

$$\mu_k = \frac{1}{k} \sum_{i=1}^{k} x_i = \frac{1}{k} \left( x_k + \sum_{i=1}^{k-1} x_i \right) = \frac{1}{k} \left( x_k + (k-1) \, \mu_{k-1} \right) = \mu_{k-1} + \frac{1}{k} \left( x_k - \mu_{k-1} \right)$$

Basta quindi tenere, per ogni stato, la stima corrente e un contatore $N(s)$ delle visite (in senso first-visit o every-visit). All’arrivo di un nuovo return $G_t$ per lo stato $S_t$:

$$N(S_t) \leftarrow N(S_t) + 1, \qquad V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)} \left( G_t - V(S_t) \right)$$

Questo aggiornamento calcola esattamente la media empirica, senza memorizzare nulla oltre a stima e contatore.

3.2 Il learning rate costante#

In alternativa al contatore si può usare un passo costante $\alpha \in (0, 1]$:

$$V(S_t) \leftarrow V(S_t) + \alpha \left( G_t - V(S_t) \right)$$

Con $\alpha$ costante non si calcola più la media empirica di tutti i campioni: si ottiene una media pesata esponenzialmente, che dà più peso alle osservazioni recenti e dimentica progressivamente quelle antiche, come una finestra mobile sfumata. Con $\alpha$ piccolo il comportamento è simile alla media vera; il vantaggio della versione a passo costante emerge nei problemi non stazionari, dove l’ambiente (o, come si vedrà nel control, la policy che genera i dati) cambia nel tempo e le osservazioni vecchie diventano fuorvianti: dimenticarle è un pregio, non un difetto.

Idea chiave: tutti gli aggiornamenti visti d’ora in avanti hanno la stessa forma: nuova stima $=$ vecchia stima $+$ passo $\times$ (target $-$ vecchia stima). In Monte Carlo il target è il return osservato $G_t$: la stima viene spinta verso il target di una frazione dell’errore corrente. Questo schema, con target diversi, sarà il filo conduttore anche del prossimo capitolo.

In parole semplici: invece di conservare tutti i voti presi e rifare la media ogni volta, si tiene la media corrente e la si corregge un po’ a ogni voto nuovo, in proporzione a quanto il voto si discosta dalla media. Con il passo $1/N$ si ottiene esattamente la media di tutti i voti; con un passo fisso si ottiene una media che “dimentica” i voti vecchi, utile se nel frattempo le cose sono cambiate.

4. Esempio: valutare una policy a blackjack#

4.1 Il problema come task episodico#

Il blackjack è un banco di prova classico per i metodi Monte Carlo. Il giocatore affronta il dealer (gli altri giocatori sono irrilevanti ai fini della vittoria): l’obiettivo è totalizzare con le proprie carte una somma maggiore di quella del dealer senza superare 21. Le figure valgono 10; l’asso vale 11 oppure 1, a scelta del giocatore secondo convenienza (un asso contato come 11 senza sforare si dice usable ace). A ogni turno il giocatore sceglie tra due azioni: hit (chiedere un’altra carta) e stick (fermarsi); se supera 21 perde immediatamente, altrimenti al termine si confronta la somma con quella del dealer. Nella versione considerata le carte sono pescate con reinserimento, quindi non c’è memoria del mazzo e lo stato non deve includere le carte uscite in passato.

La formalizzazione come MDP episodico:

• Stati (200 in totale): la somma corrente del giocatore (da 12 a 21: con somme inferiori a 12 chiedere carta non può mai far sforare, quindi la decisione è banale e quegli stati non si modellano), la carta scoperta del dealer (asso, 2, …, 10) e il possesso o meno di un usable ace; $10 \times 10 \times 2 = 200$ stati.
• Azioni: stick, hit.
• Reward: $+1$ per la vittoria, $0$ per il pareggio, $-1$ per la sconfitta, assegnato solo alla fine dell’episodio; nessun discount ($\gamma = 1$).

4.2 La valutazione Monte Carlo#

La policy da valutare è volutamente ingenua: stick se la somma è 20 o 21, altrimenti hit. Modellare analiticamente la dinamica one-step di questo problema sarebbe possibile ma laborioso; costruire un simulatore è immediato, ed è tutto ciò che serve a Monte Carlo. Generando episodi e mediando i return (con $\gamma = 1$ il return coincide con il reward finale $\pm 1$ o $0$, quindi il valore di uno stato è interpretabile come una probabilità di vittoria “netta”), dopo circa $500{.}000$ episodi la stima converge a una value function molto vicina a quella vera.

Il risultato fotografa bene la qualità della policy: il valore è alto (vicino a $+1$) solo negli stati con somma 20 o 21, dove la policy si ferma con un punteggio fortissimo; in quasi tutti gli altri stati è nettamente negativo, perché continuare a chiedere carta fino a 20 fa sforare molto spesso. È una policy rischiosa, e la value function lo quantifica stato per stato. Si osserva anche un fatto pratico, visibile nella metà superiore della figura: gli stati con usable ace sono più rari, quindi le loro stime sono più rumorose a parità di episodi; la precisione di Monte Carlo dipende da quante volte ciascuno stato viene effettivamente visitato.

In parole semplici: invece di calcolare a tavolino le probabilità del blackjack, si fa giocare al computer mezzo milione di mani con la strategia da valutare e si fa la media dei risultati da ogni situazione. Il quadro che emerge dice che la strategia “tiro finché non arrivo a 20” vince quasi solo quando ci arriva davvero, e nel frattempo sballa spessissimo.

5. Dal prediction al control: il problema dell’esplorazione#

5.1 Generalized policy iteration con Monte Carlo#

Per passare dalla valutazione all’ottimizzazione si riusa lo schema della generalized policy iteration (GPI) del capitolo precedente: alternare un passo di policy evaluation e un passo di policy improvement greedy, fino alla convergenza. Il primo istinto è sostituire la valutazione basata sul modello con la Monte Carlo prediction appena costruita e tenere invariato l’improvement. Qui però si inceppa tutto: l’improvement greedy sulla state-value function è

$$\pi'(s) = \arg\max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V(s') \right]$$

e richiede di nuovo $r$ e $p$, cioè proprio il modello che non c’è. La valutazione era diventata model-free, ma l’improvement è rimasto model-based.

La soluzione è spostarsi dalla state-value function alla action-value function. La $Q^{\pi}(s, a)$, return atteso partendo da $s$, eseguendo $a$ e seguendo poi $\pi$, si stima con lo stesso identico meccanismo Monte Carlo: si media il return osservato dopo le visite alla coppia $(s, a)$ invece che al solo stato $s$ (di nuovo in variante first-visit o every-visit). E con la $Q$ in mano l’improvement diventa banale e completamente model-free:

$$\pi'(s) = \arg\max_{a \in \mathcal{A}(s)} Q(s, a)$$

un semplice confronto tra i valori delle azioni disponibili, senza alcun lookahead attraverso il modello. Il prezzo di questo passaggio è statistico: le coppie stato-azione sono più numerose degli stati (un fattore $|\mathcal{A}|$), quindi a parità di qualità della stima servono più dati, perché ogni coppia deve essere visitata abbastanza volte.

Idea chiave: senza modello, la value function giusta da stimare è la $Q$, non la $V$: la $V$ permette di migliorare la policy solo guardando “un passo avanti” attraverso il modello, mentre la $Q$ contiene già il confronto tra le azioni e rende l’improvement un semplice $\arg\max$ su una tabella.

In parole semplici: sapere quanto vale ogni situazione non basta per scegliere la mossa, se non si sa dove porta ciascuna mossa; sapere quanto vale ogni mossa in ogni situazione invece basta e avanza: si sceglie la mossa col valore più alto e via. Per questo, quando il modello manca, si impara direttamente il valore delle mosse.

5.2 Il problema dell’esplorazione#

La stima Monte Carlo di $Q^{\pi}$ converge se ogni coppia stato-azione viene visitata infinite volte al crescere degli episodi:

$$N(s, a) \to \infty \qquad \forall s \in \mathcal{S}, \; \forall a \in \mathcal{A}(s)$$

Ed è qui che emerge il problema strutturale del control. Se la policy $\pi$ che genera i dati è deterministica, in ogni stato $s$ essa sceglie sempre la stessa azione $\pi(s)$: gli episodi conterranno solo coppie $(s, \pi(s))$, e le coppie $(s, a)$ con $a \neq \pi(s)$ non compariranno mai nei dati.

Per quelle coppie non arriverà nessun return, la stima di $Q(s, a)$ resterà priva di supporto empirico, e l’$\arg\max$ dell’improvement confronterà numeri privi di significato. Nel blackjack: con la policy “hit sotto 20”, non si osserverà mai lo stato “somma 18” seguito dall’azione stick, quindi non si potrà mai scoprire se fermarsi a 18 sia meglio.

Questa è una differenza profonda rispetto al planning con programmazione dinamica: lì il modello permette di “interrogare” qualunque coppia stato-azione a tavolino, con uno sweep sistematico su tutto lo spazio, e il problema dell’esplorazione non si pone. Quando si impara dall’interazione, invece, si conosce solo ciò che si prova: la distribuzione dei dati è determinata dalla policy seguita, e ciò che la policy non fa resta invisibile. Per far funzionare il control model-free bisogna quindi iniettare nei dati una qualche deviazione sistematica dalla policy corrente: questa componente si chiama esplorazione.

Idea chiave: per migliorare una policy servono stime di $Q$ anche per le azioni che la policy non sceglierebbe; ma i dati generati da una policy deterministica non contengono mai quelle azioni. Senza esplorazione, il control model-free non può funzionare: è un punto cardine che tornerà, in forme diverse, in tutto il reinforcement learning.

In parole semplici: se al ristorante si ordina sempre lo stesso piatto, non si saprà mai se gli altri sono migliori: il menù degli altri piatti resta una colonna di punti interrogativi. Per compilare la pagella di tutte le opzioni bisogna ogni tanto ordinare qualcosa di diverso, anche a costo di qualche delusione.

5.3 Exploring starts#

L’idea più semplice per garantire l’esplorazione agisce solo sull’inizio dell’episodio.

La casualità è confinata al primo passo, ma è sufficiente: con abbastanza episodi ogni coppia stato-azione compare come punto di partenza infinite volte, e la condizione di convergenza della stima di $Q$ è soddisfatta. Combinando exploring starts, valutazione Monte Carlo della $Q$ e improvement greedy si ottiene il primo algoritmo di control model-free, il Monte Carlo ES (Exploring Starts); una scelta efficace è eseguire l’improvement subito, episodio per episodio, sugli stati visitati, così che l’episodio successivo sia già generato dalla policy migliorata:

Inizializza: π(s) arbitraria; Q(s,a) arbitraria; Returns(s,a) ← lista vuota

Ripeti per sempre (per ogni episodio):
    Scegli S0 e A0 a caso (ogni coppia (s,a) con probabilità > 0)
    Genera un episodio da S0, A0 seguendo π
    G ← 0
    Per t = T-1, T-2, ..., 0:
        G ← γ·G + R(t+1)
        Se (St, At) non compare prima del tempo t:          # prima visita
            aggiungi G a Returns(St, At)
            Q(St, At) ← media(Returns(St, At))
            π(St) ← argmax_a Q(St, a)                       # improvement

Applicato al blackjack (dove il simulatore permette di imporre qualunque stato iniziale e qualunque prima azione), Monte Carlo ES trova una policy ottima ben diversa da quella ingenua di partenza: senza usable ace conviene essere prudenti e fermarsi molto prima di 20 (la soglia di stick dipende dalla carta scoperta del dealer); con usable ace si può giocare in modo più aggressivo e continuare a chiedere carta più a lungo, perché l’asso declassabile da 11 a 1 riduce il rischio di sforare.

Il limite di exploring starts è però evidente: richiede il controllo completo delle condizioni iniziali dell’episodio. Con un simulatore è banale (“genera una mano in cui il giocatore ha 18 e forzalo a fare stick”); in un problema reale è irrealizzabile. Nell’apprendimento di una policy di guida autonoma non si può materializzare a comando lo stato iniziale “sta piovendo, ostacolo a sinistra, velocità 100 km/h”: lo stato iniziale lo decide il mondo, non lo sperimentatore. Serve un meccanismo di esplorazione che agisca durante l’interazione, non solo al primo passo.

In parole semplici: exploring starts risolve l’esplorazione facendo iniziare ogni partita da una situazione e una prima mossa estratte a sorte, e poi lasciando giocare la strategia corrente. Funziona benissimo quando si comanda il simulatore, ma nel mondo reale non si può “apparecchiare” la situazione di partenza a piacere: serve un piano B.

5.4 Il dilemma esplorazione-sfruttamento#

Il piano B deve rispondere a una tensione che è uno dei problemi fondanti del reinforcement learning. Da un lato conviene sfruttare (exploit) la conoscenza corrente: seguire la policy migliore trovata finora, che presumibilmente incorpora quanto di buono si è appreso. Dall’altro, seguendola ciecamente non si scoprirà mai se esistono alternative migliori: bisogna esplorare (explore), cioè provare di tanto in tanto azioni diverse. L’analogia con gli scacchi è calzante: chi gioca sempre e solo la teoria dei libri non saprà mai se, in una data posizione, esiste una mossa fuori teoria più forte; chi invece sperimenta troppo spreca la maggior parte delle partite giocando male. Nessuno dei due estremi funziona: troppa esplorazione butta via le prestazioni, troppo sfruttamento congela l’apprendimento. Il problema di trovare il giusto equilibrio è noto come dilemma esplorazione-sfruttamento (exploration-exploitation dilemma), e distingue nettamente l’apprendimento dal planning: con il modello a disposizione il dilemma non esiste, perché nulla deve essere “provato” per essere conosciuto.

In parole semplici: è il dilemma del ristorante: ordinare il piatto preferito (garanzia di cena decente, zero scoperte) o provarne uno nuovo (rischio di cena mediocre, possibilità di trovare un piatto migliore)? Un agente che impara deve fare entrambe le cose, nelle giuste dosi.

6. Policy ε-soft: esplorare dentro la policy#

6.1 Policy ε-soft ed ε-greedy#

La soluzione più semplice al dilemma incorpora l’esplorazione nella policy stessa, rinunciando alle policy deterministiche. Nei capitoli sul planning ci si era limitati alle deterministiche perché negli MDP esiste sempre una policy ottima deterministica; qui la stocasticità viene reintrodotta di proposito, non per essere ottimi ma per continuare a esplorare.

Una policy $\varepsilon$-soft, per costruzione, prova prima o poi tutte le azioni in tutti gli stati raggiunti: l’esplorazione è garantita by design, a ogni passo dell’interazione e non solo all’inizio dell’episodio. Tra tutte le policy $\varepsilon$-soft, quella di interesse pratico è la più vicina possibile a una policy greedy.

Equivalentemente: con probabilità $1 - \varepsilon$ si sceglie l’azione greedy, con probabilità $\varepsilon$ si sceglie un’azione uniformemente a caso (inclusa eventualmente la greedy stessa, da cui il termine $\varepsilon / |\mathcal{A}|$ aggiuntivo). È “quasi” una policy deterministica: se $Q$ fosse la $Q^{*}$, la policy $\varepsilon$-greedy sarebbe vicina alla policy ottima quanto si vuole, con $\varepsilon$ a fare da manopola che regola la distanza dall’ottimalità in cambio di esplorazione. L’obiettivo dell’apprendimento cambia di conseguenza: non si cerca più la policy ottima deterministica, ma la migliore policy $\varepsilon$-soft.

In parole semplici: una policy $\varepsilon$-greedy quasi sempre gioca la mossa che ritiene migliore, ma con una piccola probabilità $\varepsilon$ tira a sorte tra tutte le mosse. Quel pizzico di casualità garantisce che ogni opzione venga assaggiata all’infinito, che è esattamente la condizione che serviva per stimare la $Q$ di tutte le coppie.

6.2 ε-soft Monte Carlo policy iteration#

L’algoritmo di control completo, nella versione con media incrementale, si ottiene innestando la policy $\varepsilon$-greedy nel ciclo di GPI:

Parametri: ε > 0; γ
Inizializza: Q(s,a) arbitraria; N(s,a) ← 0; π ← una policy ε-soft qualsiasi

Ripeti per sempre (per ogni episodio):
    Genera un episodio seguendo π: S0, A0, R1, ..., S(T-1), A(T-1), RT
    G ← 0
    Per t = T-1, T-2, ..., 0:
        G ← γ·G + R(t+1)
        Se (St, At) non compare prima del tempo t:          # prima visita
            N(St, At) ← N(St, At) + 1
            Q(St, At) ← Q(St, At) + (1/N(St, At))·(G − Q(St, At))
            a* ← argmax_a Q(St, a)          # a parità di valore, scelta casuale
            Per ogni a ∈ A(St):
                π(a|St) ← 1 − ε + ε/|A(St)|    se a = a*
                π(a|St) ← ε/|A(St)|            altrimenti

Rispetto a Monte Carlo ES cambiano due cose: l’episodio è generato dalla policy $\varepsilon$-greedy corrente (niente più condizioni iniziali forzate) e l’improvement aggiorna la distribuzione $\varepsilon$-greedy invece di una tabella deterministica. Se più azioni condividono il valore massimo, l’azione greedy si sceglie a caso tra esse: la scelta non influenza le garanzie. Questo pseudocodice è direttamente utilizzabile in pratica.

6.3 Il teorema di ε-greedy policy improvement#

Sostituire l’improvement greedy con quello $\varepsilon$-greedy solleva una domanda legittima: la nuova policy è davvero un miglioramento? Per le policy deterministiche la garanzia veniva dal policy improvement theorem; ne esiste un analogo per il mondo $\varepsilon$-soft.

Dimostrazione. Si valuta, in un generico stato $s$, la qualità della prima mossa scelta da $\pi'$ e giudicata con i valori di $\pi$ (per compattezza si scrive $|\mathcal{A}|$ per $|\mathcal{A}(s)|$):

$$\sum_{a} \pi'(a \mid s) \, Q^{\pi}(s, a) = \frac{\varepsilon}{|\mathcal{A}|} \sum_{a} Q^{\pi}(s, a) + (1 - \varepsilon) \max_{a} Q^{\pi}(s, a)$$

dove il primo termine raccoglie la probabilità di base $\varepsilon / |\mathcal{A}|$ distribuita su tutte le azioni e il secondo la probabilità residua $1 - \varepsilon$ concentrata sull’azione greedy. Il massimo domina qualunque media pesata: per ogni insieme di pesi $w(a) \geq 0$ con $\sum_a w(a) = 1$ vale $\max_a Q^{\pi}(s, a) \geq \sum_a w(a) \, Q^{\pi}(s, a)$. Si scelgono i pesi

$$w(a) = \frac{\pi(a \mid s) - \dfrac{\varepsilon}{|\mathcal{A}|}}{1 - \varepsilon}$$

che sono legittimi proprio perché $\pi$ è $\varepsilon$-soft: i numeratori sono non negativi ($\pi(a \mid s) \geq \varepsilon / |\mathcal{A}|$) e la loro somma è $\left( 1 - |\mathcal{A}| \cdot \frac{\varepsilon}{|\mathcal{A}|} \right) / (1 - \varepsilon) = 1$. Sostituendo:

$$\sum_{a} \pi'(a \mid s) \, Q^{\pi}(s, a) \geq \frac{\varepsilon}{|\mathcal{A}|} \sum_{a} Q^{\pi}(s, a) + (1 - \varepsilon) \sum_{a} \frac{\pi(a \mid s) - \frac{\varepsilon}{|\mathcal{A}|}}{1 - \varepsilon} \, Q^{\pi}(s, a)$$

I due termini in $\varepsilon / |\mathcal{A}|$ si cancellano e resta

$$\sum_{a} \pi'(a \mid s) \, Q^{\pi}(s, a) \geq \sum_{a} \pi(a \mid s) \, Q^{\pi}(s, a) = V^{\pi}(s)$$

In ogni stato, dunque, la prima mossa di $\pi'$ seguita da $\pi$ vale almeno quanto $V^{\pi}(s)$; per il policy improvement theorem (nella versione per policy stocastiche) questa condizione si propaga a tutti i passi futuri e implica $V^{\pi'}(s) \geq V^{\pi}(s)$ in ogni stato. $\blacksquare$

Il significato pratico: iterando valutazione Monte Carlo e improvement $\varepsilon$-greedy, ogni iterazione dell’algoritmo della sezione 6.2 produce una policy $\varepsilon$-soft non peggiore della precedente; la sequenza migliora monotonicamente e converge verso la migliore policy $\varepsilon$-soft del problema.

In parole semplici: rendere $\varepsilon$-greedy la policy rispetto ai valori appena stimati non può mai peggiorare le cose, purché si resti nella famiglia delle policy che esplorano almeno un po’. È la versione “con casualità incorporata” del solito passo di miglioramento: si sposta la preferenza sull’azione col valore più alto, mantenendo la briciola di probabilità $\varepsilon$ su tutte le altre.

6.4 GLIE: dall’ottimo ε-soft all’ottimo vero#

L’algoritmo della sezione 6.2 converge alla migliore policy $\varepsilon$-soft, che per costruzione non è la policy ottima dell’MDP: continua a sprecare probabilità $\varepsilon$ su azioni subottime. D’altra parte l’esplorazione non si può spegnere troppo presto, o le stime di $Q$ smettono di migliorare dove servirebbe. La via d’uscita è far decrescere l’esplorazione nel tempo, ma non troppo in fretta; la formalizzazione di questo compromesso è la condizione GLIE.

L’esempio canonico è proprio la policy $\varepsilon$-greedy con $\varepsilon$ che decresce come $\varepsilon_k = 1/k$ (dove $k$ è l’indice dell’episodio): la somma $\sum_k \varepsilon_k$ diverge, quindi l’esplorazione complessiva è infinita e ogni coppia continua a essere provata; al tempo stesso $\varepsilon_k \to 0$, quindi la policy diventa greedy al limite. Sotto la condizione GLIE il Monte Carlo control gode della garanzia piena: la stima converge alla action-value function ottima, $Q(s, a) \to Q^{*}(s, a)$, e di conseguenza la policy converge alla policy ottima $\pi^{*}$.

In parole semplici: all’inizio si esplora parecchio, perché non si sa nulla; man mano che le stime diventano affidabili si esplora sempre meno, fino a comportarsi da puri sfruttatori. Se la “manopola” $\varepsilon$ scende abbastanza lentamente da provare tutto infinite volte, ma scende davvero a zero, si ottiene il meglio dei due mondi: esplorazione sufficiente durante l’apprendimento e policy ottima alla fine.

7. On-policy contro off-policy#

7.1 Due modi di imparare#

Tutti gli algoritmi visti finora condividono una caratteristica implicita: la policy che genera i dati e la policy di cui si stimano i valori sono la stessa. Questo schema si chiama apprendimento on-policy. La sua conseguenza scomoda è ormai chiara: per esplorare bisogna che la policy seguita sia stocastica, quindi non si può seguire (e valutare direttamente) una policy deterministica ottima; il meglio raggiungibile senza accorgimenti come GLIE è l’ottimo nella famiglia $\varepsilon$-soft, e comunque l’agente continua a eseguire azioni casuali durante l’interazione con l’ambiente, il che in certi contesti è indesiderabile di per sé.

L’idea alternativa è disaccoppiare i due ruoli.

L’off-policy scioglie elegantemente il dilemma esplorazione-sfruttamento: l’esplorazione la fa la behavior policy, che può permettersi di essere casuale quanto serve; l’ottimalità la persegue la target policy, che non deve più contenere alcuna componente esplorativa. In più, l’off-policy permette di imparare da dati generati da altri: log storici, dimostrazioni umane, policy di sicurezza già operative.

In parole semplici: on-policy è imparare a giocare giocando in prima persona con la propria strategia, difetti esplorativi inclusi; off-policy è imparare la strategia che si vorrebbe avere guardando partite giocate da qualcun altro, anche da uno che gioca a caso. Il secondo schema separa chi raccoglie l’esperienza da chi ne beneficia.

7.2 Target, behavior e la condizione di copertura#

L’esempio guida delle slide è un gridworld: un gatto deve raggiungere la casa. La target policy è deterministica e ragionevole (sempre a destra, poi in su lungo l’ultima colonna); la behavior policy è uniforme su tutte le direzioni, cioè puro vagabondaggio esplorativo. La domanda dell’off-policy è: si possono usare le passeggiate casuali del gatto per capire quanto rende la strategia deterministica?

La risposta è sì, ma non gratis: c’è un vincolo di compatibilità tra le due policy. Si può apprendere solo una target policy che sia coperta dalla behavior policy:

$$\pi(a \mid s) > 0 \implies b(a \mid s) > 0 \qquad \forall s, a$$

Ogni azione che la target policy potrebbe eseguire deve avere probabilità positiva di essere eseguita anche dalla behavior policy: altrimenti nei dati mancheranno proprio le transizioni che servono per valutarla. Il gridworld del gatto rende l’idea anche al contrario: se la behavior fosse deterministica e percorresse sempre lo stesso corridoio, i dati conterrebbero un solo tubo di coppie stato-azione, e sarebbe impossibile valutare una target che passi per il centro della griglia, perché nessuna delle sue azioni sarebbe mai stata osservata. È lo stesso principio dell’esplorazione, riletto in chiave off-policy: ciò che la behavior policy non prova mai, nessuna target policy potrà mai impararlo. In pratica la condizione si garantisce scegliendo come behavior una policy $\varepsilon$-soft: probabilità positiva su tutte le azioni, copertura di qualunque target.

In parole semplici: si può imparare solo dalle esperienze che qualcuno ha effettivamente fatto. Se il dimostratore non prova mai una certa mossa in una certa situazione, nessuna quantità di matematica potrà dire quanto vale quella mossa: la behavior policy deve “coprire” tutte le mosse che interessano alla target.

8. Importance sampling#

8.1 Il principio: cambiare distribuzione a una media#

Resta da capire come si possano usare dati generati da $b$ per stimare i valori di $\pi$: mediare direttamente i return osservati stimerebbe $V^{b}$, non $V^{\pi}$. Lo strumento è una tecnica statistica generale, l’importance sampling, che permette di stimare il valore atteso rispetto a una distribuzione usando campioni estratti da un’altra.

Sia $X$ una variabile aleatoria e siano $P$ e $Q$ due distribuzioni. Il valore atteso sotto $P$ si può riscrivere facendo comparire $Q$:

$$\mathbb{E}_{X \sim P}\left[ X \right] = \sum_{x} x \, P(x) = \sum_{x} x \, \frac{P(x)}{Q(x)} \, Q(x) = \mathbb{E}_{X \sim Q}\left[ X \, \frac{P(X)}{Q(X)} \right]$$

(purché $Q(x) > 0$ ovunque $P(x) > 0$: è esattamente la condizione di copertura). Il rapporto $\rho(x) = P(x)/Q(x)$ pesa ogni campione: amplifica i valori che $P$ renderebbe più frequenti di quanto faccia $Q$, e smorza quelli sovra-rappresentati da $Q$. La versione campionaria: dati $x_1, \dots, x_n$ estratti da $Q$,

$$\mathbb{E}_{X \sim P}\left[ X \right] \approx \frac{1}{n} \sum_{i=1}^{n} \rho(x_i) \, x_i$$

una media empirica in cui ogni osservazione è corretta dal proprio peso.

In parole semplici: se i dati arrivano dalla distribuzione “sbagliata”, non si buttano: si ripesano. Un’osservazione che sotto la distribuzione giusta sarebbe stata due volte più probabile conta doppio; una che non sarebbe mai potuta accadere conta zero. Con i pesi giusti, la media dei dati sbagliati stima la quantità giusta.

8.2 Il coefficiente ρ per la policy evaluation#

Nel contesto Monte Carlo la variabile da mediare è il return $G$ e la “distribuzione” è quella sulle traiettorie indotta dalla policy. La probabilità di osservare, a partire da $S_t$, la sequenza di azioni e stati $A_t, S_{t+1}, A_{t+1}, \dots, S_T$ seguendo $\pi$ è

$$\mathbb{P}\left[ A_t, S_{t+1}, \dots, S_T \mid S_t, \pi \right] = \prod_{k=t}^{T-1} \pi(A_k \mid S_k) \, p(S_{k+1} \mid S_k, A_k)$$

il prodotto, passo dopo passo, della probabilità di scegliere l’azione osservata e della probabilità di transizione verso lo stato osservato (i reward non aggiungono fattori dipendenti dalla policy: dipendono solo da stato e azione). Il peso di importance sampling di una traiettoria è il rapporto tra la sua probabilità sotto la target e sotto la behavior:

$$\rho_{t:T-1} = \frac{\prod_{k=t}^{T-1} \pi(A_k \mid S_k) \, p(S_{k+1} \mid S_k, A_k)}{\prod_{k=t}^{T-1} b(A_k \mid S_k) \, p(S_{k+1} \mid S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}$$

Il punto cruciale è la cancellazione delle probabilità di transizione: la dinamica $p$ compare identica al numeratore e al denominatore (la traiettoria osservata è la stessa) e sparisce dal rapporto. Il peso dipende solo dalle due policy, entrambe note per costruzione: il metodo resta completamente model-free. La value function della target policy si stima allora come media pesata dei return osservati seguendo la behavior:

$$V^{\pi}(s) \approx \frac{1}{n} \sum_{i=1}^{n} \rho_i \, G_i$$

dove $G_i$ è il return dell’$i$-esima visita a $s$ nei dati generati da $b$, e $\rho_i$ il peso della corrispondente porzione di traiettoria.

Un esempio chiarisce la meccanica dei pesi. Sia la target policy $\pi$ deterministica e la behavior $b$ uniforme su 4 azioni ($b(a \mid s) = 0{,}25$ per ogni azione). Se in un tratto di traiettoria di due passi la behavior esegue esattamente le due azioni che $\pi$ prescrive, il peso è

$$\rho = \frac{1 \cdot 1}{0{,}25 \cdot 0{,}25} = 16$$

quel return, raro sotto $b$ ma certo sotto $\pi$, viene amplificato di un fattore 16. Se invece la traiettoria contiene anche una sola azione che $\pi$ non sceglierebbe, il numeratore contiene uno zero e $\rho = 0$: quel return viene escluso del tutto dalla media, perché sotto la target policy quella traiettoria non potrebbe mai realizzarsi.

Idea chiave: il peso $\rho$ è il prodotto, lungo la traiettoria, dei rapporti $\pi / b$ sulle sole azioni: la dinamica dell’ambiente si semplifica e non serve conoscerla. Traiettorie compatibili con la target vengono amplificate, traiettorie incompatibili azzerate: la media pesata dei return “vissuti da $b$” diventa una stima dei return “che avrebbe vissuto $\pi$”.

In parole semplici: guardando le partite di un giocatore che muove a caso, si tengono solo i tratti di partita in cui, per caso, ha giocato esattamente come avrebbe giocato la strategia che interessa, e li si conta molte volte per compensarne la rarità; i tratti dove ha fatto mosse “fuori strategia” si scartano. Così le partite di un altro raccontano quanto rende la propria strategia.

8.3 Ordinary e weighted importance sampling#

La media pesata dei return si può normalizzare in due modi diversi, e la scelta ha conseguenze statistiche importanti.

Le proprietà sono speculari:

• lo stimatore ordinario è unbiased (il suo valore atteso è esattamente $V^{\pi}(s)$ per ogni $n$), ma ha varianza alta, in linea di principio anche illimitata: i pesi $\rho$, essendo prodotti di rapporti, possono assumere valori enormi, e con pochi campioni la stima può essere lontanissima dal valore vero;
• lo stimatore pesato è biased (per esempio con $n = 1$ restituisce semplicemente $G_1$, che è un campione di $V^{b}$, non di $V^{\pi}$), ma il bias converge a zero al crescere di $n$; in compenso ha varianza molto più bassa: essendo una media pesata dei return osservati, non può mai uscire dall’intervallo dei $G_i$, e i campioni improbabili sotto la target vengono ridimensionati anche al denominatore. In pratica parte subito con errori piccoli ed è quasi sempre preferito.

In parole semplici: la versione ordinaria è il contabile onesto ma nervoso: in media dice sempre il valore giusto, ma con pochi dati può sparare numeri assurdi, perché i pesi giganteschi la sballottano. La versione pesata è più prudente: all’inizio è un po’ di parte, ma dà subito numeri sensati, e con abbastanza dati la sua distorsione svanisce.

8.4 Off-policy Monte Carlo prediction e control#

Lo pseudocodice della off-policy every-visit MC prediction con ordinary importance sampling, in forma incrementale (il peso $W$ accumula i rapporti $\pi / b$ procedendo all’indietro, così che al tempo $t$ valga $W = \rho_{t:T-1}$):¹

Input: behavior policy b; target policy π (con copertura: π(a|s)>0 ⟹ b(a|s)>0)
Inizializza: V(s) arbitraria; N(s) ← 0

Ripeti per sempre (per ogni episodio):
    Genera un episodio seguendo b: S0, A0, R1, ..., S(T-1), A(T-1), RT
    G ← 0;  W ← 1
    Per t = T-1, T-2, ..., 0:
        G ← γ·G + R(t+1)
        W ← W · π(At|St) / b(At|St)
        N(St) ← N(St) + 1
        V(St) ← V(St) + (1/N(St)) · (W·G − V(St))

Si noti che se a un certo passo $W$ diventa zero (la behavior ha eseguito un’azione che la target non farebbe mai), tutti i pesi dei passi precedenti dell’episodio resteranno zero: i return corrispondenti entrano nella media con contributo nullo, coerentemente con l’esclusione vista sopra. La stessa idea si estende dal prediction al control off-policy: si stima la $Q$ della target policy con importance sampling e, dopo ogni episodio, si applica l’improvement rendendo la target greedy rispetto alla $Q$ corrente. C’è solo un’avvertenza: quando la target cambia, cambiano anche i coefficienti $\rho$ con cui verranno pesati gli episodi successivi, perché $\rho$ dipende da $\pi$. Il risultato è un algoritmo che si comporta in modo esplorativo (tramite $b$, per esempio $\varepsilon$-soft) e impara al tempo stesso una policy ottima deterministica: la separazione dei ruoli promessa dall’off-policy.

9. I limiti dei metodi Monte Carlo#

I metodi Monte Carlo raggiungono l’obiettivo dichiarato: policy evaluation e control senza alcuna conoscenza del modello, con garanzie di convergenza. Hanno però limiti strutturali che motivano la famiglia di metodi del prossimo capitolo:

• solo task episodici: il target dell’aggiornamento è il return completo $G_t$, che esiste solo se l’episodio termina; i problemi continui sono fuori portata per definizione;
• apprendimento solo a fine episodio: nulla viene appreso finché l’episodio non si chiude. Se gli episodi sono lunghi l’informazione viene sfruttata con grande ritardo; peggio, se con la policy iniziale (tipicamente casuale) raggiungere lo stato terminale è un evento raro, l’apprendimento fatica perfino a iniziare, perché i primi episodi utili tardano ad arrivare;
• alta varianza: il return campionato accumula la casualità dell’intera traiettoria, cioè di una lunga sequenza di azioni, transizioni e reward; lo stimatore è (nella versione first-visit) unbiased, ma molto rumoroso, e servono molti episodi per ottenere stime affidabili. Nel caso off-policy con ordinary importance sampling la varianza può diventare estrema, perché i pesi $\rho$ sono prodotti di rapporti che possono esplodere;
• nessun riuso della struttura ricorsiva: Monte Carlo ignora l’equazione di Bellman, cioè il legame tra il valore di uno stato e quello dei suoi successori; ogni stima è costruita da zero sui return, senza propagare l’informazione tra stati vicini.

Il prossimo capitolo introduce il temporal-difference learning, che affronta esattamente questi punti: aggiornamenti a ogni passo (anche in task continui) e varianza molto più bassa, al prezzo di un po’ di bias; il confronto sistematico tra Monte Carlo, TD e programmazione dinamica sarà sviluppato lì.

In parole semplici: Monte Carlo è affidabile ma paziente all’eccesso: aspetta la fine di ogni partita per imparare, ha bisogno che le partite finiscano, e ogni singola partita è un campione molto rumoroso. Su problemi lunghi o senza un vero traguardo serve qualcosa che impari strada facendo.

10. Esercizi svolti in stile esame#

10.1 First-visit ed every-visit su un episodio (γ = 1)#

Testo. In un MDP episodico con $\gamma = 1$ si osserva, seguendo la policy $\pi$, il seguente episodio (per ogni $t$ sono riportati lo stato visitato e il reward ricevuto al passo successivo):

L’episodio termina dopo $T = 5$ passi. Stimare $V^{\pi}$ per i tre stati con Monte Carlo first-visit ed every-visit.

Svolgimento

Si calcolano i return all’indietro con la ricorsione $G_t = R_{t+1} + \gamma \, G_{t+1}$, partendo da $G_T = 0$:

$$G_4 = 1, \qquad G_3 = 2 + G_4 = 3, \qquad G_2 = -2 + G_3 = 1, \qquad G_1 = 0 + G_2 = 1, \qquad G_0 = 1 + G_1 = 2$$

Visite per stato: $s_1$ al tempo $0$; $s_2$ ai tempi $1$ e $3$; $s_3$ ai tempi $2$ e $4$.

First-visit (si usa solo la prima occorrenza di ogni stato):

$$V(s_1) = G_0 = 2, \qquad V(s_2) = G_1 = 1, \qquad V(s_3) = G_2 = 1$$

Every-visit (si mediano i return di tutte le occorrenze):

$$V(s_1) = 2, \qquad V(s_2) = \frac{G_1 + G_3}{2} = \frac{1 + 3}{2} = 2, \qquad V(s_3) = \frac{G_2 + G_4}{2} = \frac{1 + 1}{2} = 1$$

Le due stime differiscono su $s_2$ ($1$ contro $2$): la prima visita a $s_2$ incorpora anche il tratto di ciclo con reward negativo, la seconda no, e l’every-visit media entrambe le prospettive. Con un solo episodio nessuna delle due stime è “quella giusta”: sono entrambi stimatori legittimi che convergono allo stesso limite al crescere degli episodi.

10.2 Più episodi con discount (γ = 0,5)#

Testo. In un MDP episodico con $\gamma = 0{,}5$ si osservano, sotto la policy $\pi$, due episodi:

Episodio 1: $A \xrightarrow{+2} B \xrightarrow{0} A \xrightarrow{+4} \text{terminale}$

Episodio 2: $B \xrightarrow{+2} A \xrightarrow{-2} \text{terminale}$

(la notazione $X \xrightarrow{r} Y$ indica che dallo stato $X$ si riceve reward $r$ e si transita in $Y$). Stimare $V^{\pi}(A)$ e $V^{\pi}(B)$ con first-visit ed every-visit MC.

Svolgimento

Return dell’episodio 1, all’indietro ($T = 3$):

$$G_2 = 4, \qquad G_1 = 0 + 0{,}5 \cdot 4 = 2, \qquad G_0 = 2 + 0{,}5 \cdot 2 = 3$$

Le visite sono: $A$ ai tempi $0$ e $2$, $B$ al tempo $1$. Return dell’episodio 2 ($T = 2$):

$$G_1 = -2, \qquad G_0 = 2 + 0{,}5 \cdot (-2) = 1$$

con $B$ al tempo $0$ e $A$ al tempo $1$.

First-visit: per $A$ si usano $G_0 = 3$ (episodio 1, prima visita al tempo $0$) e $G_1 = -2$ (episodio 2, prima e unica visita); per $B$ si usano $G_1 = 2$ (episodio 1) e $G_0 = 1$ (episodio 2):

$$V(A) = \frac{3 + (-2)}{2} = 0{,}5, \qquad V(B) = \frac{2 + 1}{2} = 1{,}5$$

Every-visit: per $A$ si aggiunge anche la seconda visita dell’episodio 1 ($G_2 = 4$); per $B$ non cambia nulla, perché non ha mai visite ripetute:

$$V(A) = \frac{3 + 4 + (-2)}{3} = \frac{5}{3} \approx 1{,}67, \qquad V(B) = \frac{2 + 1}{2} = 1{,}5$$

Schema operativo da esame: (1) calcolare i return all’indietro episodio per episodio con $G \leftarrow R + \gamma G$; (2) elencare le visite di ogni stato distinguendo le prime dalle successive; (3) mediare i return selezionati secondo la variante richiesta. L’errore tipico da evitare è dimenticare il discount nei return intermedi o contare due volte la stessa visita nella variante first-visit.

10.3 Importance sampling: calcolo dei pesi e delle due stime#

Testo. In un MDP con due azioni per stato, la behavior policy è uniforme, $b(a \mid s) = 0{,}5$ per ogni $a$ e $s$, e la target policy $\pi$ è deterministica. Si osservano due episodi che partono dallo stato $s_0$:

• Episodio 1: tre passi, in cui le azioni eseguite coincidono in ogni stato visitato con quelle prescritte da $\pi$; return osservato $G_1 = 4$;
• Episodio 2: al primo passo la behavior esegue in $s_0$ un’azione diversa da $\pi(s_0)$; return osservato $G_2 = 2$.

Stimare $V^{\pi}(s_0)$ con ordinary e weighted importance sampling.

Svolgimento

Peso dell’episodio 1: ogni fattore vale $\pi / b = 1 / 0{,}5 = 2$, e i passi sono tre:

$$\rho_1 = \left( \frac{1}{0{,}5} \right)^3 = 8$$

Peso dell’episodio 2: il primo fattore ha numeratore $\pi(a \mid s_0) = 0$ (azione mai scelta dalla target), quindi

$$\rho_2 = 0$$

Stima ordinaria (si divide per il numero di episodi, $n = 2$):

$$V(s_0) = \frac{\rho_1 G_1 + \rho_2 G_2}{2} = \frac{8 \cdot 4 + 0 \cdot 2}{2} = 16$$

Stima pesata (si divide per la somma dei pesi):

$$V(s_0) = \frac{\rho_1 G_1 + \rho_2 G_2}{\rho_1 + \rho_2} = \frac{32 + 0}{8} = 4$$

Il confronto è istruttivo. La stima pesata restituisce $4$, cioè il return dell’unico episodio compatibile con la target: un valore nella scala giusta. La stima ordinaria restituisce $16$, fuori scala rispetto a qualunque return osservabile: con soli due episodi il peso $8$ dell’episodio compatibile non è ancora “compensato” dai molti episodi a peso zero che la behavior produrrà in futuro (in media solo un episodio su otto segue le tre scelte di $\pi$, ed è amplificato di un fattore $8$: sul lungo periodo i conti tornano e lo stimatore è unbiased, ma sul breve la varianza è enorme). È la fotografia numerica del trade-off della sezione 8.3: ordinaria unbiased ma instabile, pesata leggermente biased ma subito ragionevole.

Glossario#

---

1. Lo pseudocodice della slide corrispondente (p. 31 del deck) accumula il return come $G \leftarrow \gamma W G + R_{t+1}$ e aggiorna $W$ solo dopo averlo usato: in quella forma il rapporto $\pi/b$ del passo corrente non viene mai applicato al return appena registrato, e i rapporti dei passi successivi compaiono con potenze spurie. Qui si riporta la versione corretta, in cui al momento dell’uso $W$ vale esattamente $\rho_{t:T-1}$.↩︎

Dispensa Machine Learning · Politecnico di Milano